package com.kiven.quicksort;

import java.util.Random;

public class TestQuickSort {
	private MyComparator mc = new MyComparator();
	/*public void quickSort(int[] src, int begin, int end) {
		if (begin < end) {
			int key = src[begin];
			int i = begin;
			int j = end;
	
			while (i < j) {
				while (i < j && src[j] > key) {
					j--;
				}
				if (i < j) {
					src[i] = src[j];
					i++;
				}
				while (i < j && src[i] < key) {
					i++;
				}
				if (i < j) {
					src[j] = src[i];
					j--;
				}
			}
		
				src[i] = key;
		
				quickSort(src, begin, i - 1);
				quickSort(src, i + 1, end);
			}

	}*/

public void quickSort(Object[] keyset,Object[] values,int left,int right) {
	if(left < right) {
		Object pivotKey,pivotValue;
		int i = left;
		int j = right;
		pivotKey = keyset[left];
		pivotValue = values[left];
		
		while(i<j) {
			while(i<j && mc.compare(keyset[j], pivotKey)>0) {
				j--;
			}
			if(i<j) {
				keyset[i] = keyset[j];
				values[i] = values[j];
				i++;
			}
			while(i<j && mc.compare(keyset[i], pivotKey)<0) {
				i++;
			}
			if(i<j) {
				keyset[j] = keyset[i];
				values[j] = values[i];
				j--;
			}
			
			keyset[i] = pivotKey;
			values[i] = pivotValue;
			
			quickSort(keyset,values,left,i-1);
			quickSort(keyset,values,i+1,right);
		}
	}
	
}
	
	public static void main(String[] args) {
		Object[] keyset,values;
		keyset = new Object[]{1,1,1,1,1};
		values = new Object[]{"LI","one",300,1,"HHH"};
		
		System.out.println("排序前");
		for(int i=0; i<keyset.length; i++) {
			System.out.println("键：" +keyset[i] +"   值：" +values[i]);
		}
		
		TestQuickSort qs = new TestQuickSort();
		
		//调用快速排序递归
		qs.quickSort(keyset,values,0,keyset.length-1);
		
		System.out.println("快速排序实现-----排序后");
		for(int i=0; i<keyset.length; i++) {
			System.out.println("键：" +keyset[i] +"   值：" +values[i]);
		}
	}
}
